package problems.practice;

import utils.beans.ListNode;

/**
 * 剑指 Offer II 026. 重排链表
 * <p>https://leetcode.cn/problems/LGjMqU/</p>
 *
 * @author habitplus
 * @since 2022/10/17 18:00
 */
public class Offer_2_T026 {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        ListNode low = head, fast = head.next, tmp1, tmp2;

        // 在中点处切割链表
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
        }
        fast = low.next;
        low.next = null;

        // 翻转链表
        low = null;
        while (fast != null) {
            tmp1 = fast.next;
            fast.next = low;
            low = fast;
            fast = tmp1;
        }

        // 合并链表
        fast = low;
        low = head;
        while (low != null && fast != null) {
            tmp1 = low.next;
            tmp2 = fast.next;
            low.next = fast;
            fast.next = tmp1;
            fast = tmp2;
            low = tmp1;
        }
    }
}
